/**
 * com.future CO.,ltd.
 */

package com.future;

import java.util.HashMap;
import java.util.Map;

/**
 * 类说明：
 */
public class Solution_138 {

    public static void main(String[] args) {

        Node head = new Node(0);
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        head.random = node2;
        node1.random = node3;
        node3.random = node4;
        head.next = node1;
        head.next.next = node2;
        head.next.next.next = node3;
        head.next.next.next.next = node4;
        print(head);
        System.out.println("=====================");
        Node node = copyRandomList_v1(head);
        print(node);
    }

    public static void print(Node head) {
        if (head == null) {
            return;
        }
        while (head != null) {
            System.out.println("--" + head.val);

            Node tmp = head;
            while (tmp.random != null) {
                System.out.println("----" + tmp.random.val);
                tmp = tmp.random;
            }

            head = head.next;
        }
    }

    /**
     * 用容器的方法
     * 最简单，做容易理解的方式
     *
     * @param head
     * @return
     */
    public static Node copyRandomList_v1(Node head) {
        if (head == null) {
            return head;
        }
        Map<Node, Node> map = new HashMap<>();
        Node op1 = head;
        while (op1 != null) {
            map.put(op1, new Node(op1.val));
            op1 = op1.next;
        }
        Node op2 = head;
        while (op2 != null) {
            /**
             * 容易错
             */
            map.get(op2).random = map.get(op2.random);
            map.get(op2).next = map.get(op2.next);
            op2 = op2.next;
        }
        return map.get(head);
    }


    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
}
